In wireless systems messages, i.e. a sequence of symbols drawn from a signaling set, are transmitted in coded form. That is, the message is reduced to binary symbols in a series of codewords. The codewords are grouped into frames that are ultimately transmitted. The process of converting a message into a frame or series of frames for transmission is generally denominated coding.
Since any wireless network is subject to noise and other conditions (e.g. interference) influencing the transmitted signal, frames are often not received, are sufficiently distorted so that the encoded message cannot be decoded, or are decoded incorrectly. A failure to decode is recognized by detection algorithms, such as special parity check algorithms, that operate on a series of parity symbols derived from and appended to the transmitted codewords. Some errors in a received frame are correctable using error correction algorithms. To address the remaining uncorrected errors, expedients such as automatic repeat request (ARQ) schemes are employed. In these approaches, if a frame is not received or an unresolvable error is detected at the receiver, a message (generally denominated a negack) is sent to the transmitter requesting retransmission.
Many coding techniques have been developed for transforming a message into a frame or series of frames that has a further improved probability of reception and correct decoding. One such approach has been denominated low density parity codes (LDPC)—a class of linear block codes. In LDPC, the binary symbols representing a message are each associated with a variable node. Thus as shown in the illustrative LDPC code of FIG. 1, eight variable nodes (c1 through c8) are present. Each variable node corresponds to one bit of a codeword. Message bits (in a systematic code) or bits representing the message (in a non-systematic code) are associated with a portion (less than all) of the variable nodes, e.g. c2, c4, c6, and c7. Accordingly, in the example of FIG. 1, four message bits z1 through z4 are associated respectively with c2, c4, c6, and c7. (There are more variable nodes than message bits to provide the redundancy needed for error correction.) The chosen number of variable nodes is correlated with a chosen number of check nodes. Thus in the example of FIG. 1 there are four check nodes f1 through f4, and as shown by connecting lines, four check nodes are associated with each variable node. Similarly, each check node in the example is associated with four variable nodes. A LDPC code is classified by the number of variable nodes and check nodes employed in the scheme as well as the number of, and identity of, variable nodes associated with each check node, and the number of check nodes associated with each variable node. The scheme of FIG. 1 is further denominated regular, as contrasted to irregular, since the number of variable nodes associated with each check node is the same for each check node and the number of check nodes associated with each variable node is also the same for each variable node.
The LDPC coding scheme also requires that only a defined codeword be transmitted. A word is a codeword only if it has an appropriate length (8 bits in the example) and satisfies specific parity checks, i.e., the sum modulo 2 at each check node of the associated variable nodes is 0 (or some other fixed value). (Thus for an eight variable node, 4 check node scheme there are at least 28/24=16 codewords.) In the illustration of FIG. 1 the sum of check nodes c1, c3, c4, and c8 (those associated with f1) is 0. Similarly the corresponding sum at each other check node is zero. For example, in systematic codes a subset of the variable nodes corresponds to the information bits and the remaining transmitted bits of the codeword are chosen to make the parity checks consistent.
It is, however, desirable to transmit the fewest number of bits that yield upon reception an acceptable error rate. For LDPC codes a puncturing approach is often employed to increase transmitted bit rate while maintaining an acceptable error rate. In puncturing only a portion of a LDPC codeword sequence is transmitted at each transmission interval. Thus FIG. 2 shows a sequence of transmission intervals (22 through 25) for codeword 21. The bit sequence 21 is parsed and a portion 22 is transmitted. If such transmission is sufficient to allow decoding, the next sequence is addressed. If the receiver is unable to discern the message, a further portion 23 of the first sequence is transmitted. The cycle is continued for example by sending portion 24 in a third transmission and if needed portion 25 in a fourth transmission until the sequence is decoded at the receiver. The number of bits in each transmission, the particular bits chosen for transmission, and the signal intensity of such transmission is adjusted to yield the desired performance for the scheme.
The use of LDPC codes with puncturing has proven beneficial for the transmission of wireless messages. Nevertheless, not all LDPC codes perform equally well. (The typical metric of performance is throughput as measured by the average number of user data bits accepted at the receiver in the time required for transmission of a single bit.) Generally irregular LDPC codes after optimization perform better than regular codes. However, among irregular codes performance varies greatly. Additionally, the computational complexity involved in decoding varies substantially among such codes. As a further complicating factor, LDPC codes generally do not perform well on transmission channels having substantial interference and fail when the capacity of the channel is smaller than the rate of the code.
Various other codes have been developed in the hope of improving throughput. One such robust class designed for, and most often applied to, optical communication systems is Raptor codes. Such codes have been thought to have the potential for performing better than LDPC codes when the communication channel is noisy. In a Raptor code an LDPC or turbo (as described in Raptor Codes, Amin Shokrollahi Digital Fountain Technical Report DF-2003-06-001) codeword is further encoded. A probability, Ωd is assigned to each integer, d, where d corresponds to an integer from 1 to the number of bits in the LDPC codeword frame. A series of numbers, d, is chosen before each codeword frame transmission. The choosing algorithm is designed such that the likelihood of choosing a specific number is commensurate with its assigned probability. The number d, chosen is employed as the number of distinct bits of the LDPC codeword sequence chosen at random that are summed with subsequent transmission of such sums in a stream. Since the transmitter and receiver are synchronously running the same version of a random number generator for d, the receiver knows the sequence of d's chosen at the transmitter and which corresponding d bits of the LDPC code bits are chosen. With the knowledge of the chosen d, decoding is attempted upon reception.
In a Raptor scheme, the likelihood of decoding depends on the parameters of 1) signal transmission intensity, and 2) the transmitted number of bits (representing sums) per underlying LDPC frame. If decoding is not achieved for the parameter chosen, a new series of sums are formed for the non-decoded bits by choosing a new series of d's. The process of choosing a series of d's as well as a corresponding number of bits and sending the corresponding sums is continued until reception and decoding is accomplished.
Thus in the Raptor approach puncturing is not employed. Instead, an expedient involving assigned probabilities is used. The efficacy of the chosen Raptor code scheme depends on a variety of variables. For example, the chosen set of Ωds, the underlying LDPC code, transmission intensity and the frame size all affect the effectiveness of the code.